The present invention relates to a method and a circuit for digital signal processing to achieve a so-called "Discrete Cosine Transform" (DCT).
In general, an integral transform provides a way to reversibly transform one function (or set of data) into another function. (See generally, e.g., Arfken, MATHEMATICAL METHODS FOR PHYSICISTS (2.ed. 1970); Bateman et al., TABLES OF INTEGRAL TRANSFORMS (1954); both of which are hereby incorporated by reference.) Integral transforms are a fundamental tool of applied mathematics, but typically require a large amount of calculation to implement in practice. Thus, digital implementations of integral transforms have been intensively studied. (See generally, e.g., R. Hamming, NUMERICAL METHODS FOR SCIENTISTS AND ENGINEERS (2.ed. 1973), which is hereby incorporated by reference. A digital implementation of an integral transform is necessarily "discrete," i.e. is applied to data points which are separated by some finite interval, as opposed to the continuous transformations implied by the original equations of abstract integral transforms. Integral transforms may transform a one-dimensional data array to a one-dimensional coefficient array, or may be used to relate two-dimensional data and coefficient arrays. Of course, the transforms most useful for image and video applications are typically two-dimensional or higher.)
Interest in efficient computation accelerated greatly after the publication of various Fast Fourier Transform (FFT) procedures in the 1960s and 1970s. (See generally, e.g., Cooley & Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series," 19 MATH. COMPUT. 297 (1965), and papers citing this paper, all of which are hereby incorporated by reference.)
Integral transforms are especially attractive for compression and analysis of image and video data. For video compression and coding, the objective is to filter out "inessential" image data. Human visual perception does not make use of the full bandwidth of video images, so that, in principle, it should be possible to achieve a very large reduction in image data with very slight reduction in perceived quality. Reduction in data volume leads to substantial product advantages, such as faster transmission and smaller storage requirements for video images, and/or use of lower-bandwidth channels for transmission of images. However, it is not easy to achieve such compression by simple filtering of the image. The attraction of integral transform operations is that, by defining a suitable transform operation, it may be possible to perform a simple filtering operation in the transform domain (i.e. on the transformed data) which will achieve large data compression with minimal degradation of perceived quality. Similarly, for image recognition and understanding problems, it is desirable to find a transform domain where the "essential" features of the image can be efficiently filtered for rapid comparison with recognition templates. General background discussion may be found, for example, in Rosenfeld & Kak, DIGITAL PICTURE PROCESSING (2.ed. 1982); Rabiner & Gold, THEORY AND APPLICATIONS OF DIGITAL SIGNAL PROCESSING (1975); PICTURE PROCESSING AND DIGITAL FILTERING (2.ed. Huang 1979); all of which are hereby incorporated by reference.
In particular, it has been suggested that the Discrete Cosine Transform (DCT) may be particularly advantageous for image transformation. See Ahmed et al., "Discrete Cosine Transform," 23 IEEE TRANS'NS ON COMPUTERS 90 (January 1974); Kamangar et al., "Fast Algorithms for the 2-D Discrete Cosine Transform," 31 IEEE TRANS'NS ON COMPUTERS 899 (September 1982). These and other articles of interest are collected in DIGITAL IMAGE PROCESSING AND ANALYSIS (ed. Chellappa & Sawchuk 1985), which is hereby incorporated by reference in its entirety.
This type of transformation makes the correspondence between a matrix (or block) of digital input values and a matrix of digital output values (or coefficients). (The term "coefficients" will be frequently used, in the present application, for the transformed data. This terminology is intended to help prevent confusion between the image data set and the transformed data set. This transformation is particularly useful for compressing images to be transmitted at a higher rate than the rate that would be possible if the corresponding signals were transmitted without transformation.) The cosine transform of itself does not achieve any data compression; the compression is performed by an encoder positioned downstream of the transformation circuit. However, the transformation circuit makes compression easier, by feeding the encoder transformed data that can be safely compressed. Such transformation circuits are particularly useful for digital transmission of black and white or color images, and the preferred embodiment will be described with reference to such applications. Thus, the matrix of digital input values will correspond to a pixel matrix. (Normal video image formats are closely related to the operation of a raster-scanned cathode-ray tube. Thus, a video image includes a long series of successive frames (possibly accompanied by audio or character data at a low data rate). Each frame includes multiple lines of image data, and each line includes a fixed number of pixels. (In analog images, it is more accurate to speak of a maximum number of pixels, since the actual information content of the image will be affected by the image degradation during transmission and reception.) The gray level of each pixel, and its color components, will be specified by a bit resolution which varies widely, depending on the format used. For example, a black and white character display needs only 1 bit per pixel, but a "true-color" display uses 24 bits per pixel. The frame rate is chosen to be high enough to reduce flicker. For example, the NTSC television standard provides an apparent frame rate of 60 Hz; but this is achieved by transmitting interlaced half-frames alternately, so that the true frame rate is about 30 frames per second.)
The cosine transform is preferably performed block-by-block, and not on the whole image plane at once. That is, to achieve the cosine transform, the image (or frame) to be transmitted is arranged into blocks of pixels, e.g. the N.sup.2 pixels in an area of N rows and N columns. Each pixel in each block is represented by a digital value, for example a 8-bit coded value. This value corresponds, for example, to the luminance and/or chrominance components of a pixel. Partitioning the image in this fashion vastly reduces the volume of calculations which must be performed.
The cosine transform makes the correspondence between the block of N.times.N pixels and a block of N.times.N coefficients. The value of the pixel having coordinates x and y in the block is called f(x,y). F(u,v) designates the coefficient calculated according to the cosine transform and positioned at the intersection of line u and column v in the transformed block. In the most usual case, N=8, so that x, y, u and v will range from 0 to 7.
In the following description, only this specific example of 8.times.8 pixel blocks will be considered. Those skilled in the art will be able to easily calculate or find in specialized literature corresponding formulas for N.times.N pixel blocks. Thus, in the specific example considered, a cosine transform is disclosed by the following relation: ##EQU2## In this formula: K is a standardization coefficient which is expressed as an integral power of 2;
x,y are spatial coordinates of a pixel of the initial block; PA1 u,v are coordinates of a coefficient of the transformed block; PA1 f(x,y) is the value of a pixel of the initial block; PA1 F(u,v) is the value of a coefficient of the cosine transform; PA1 c(u), c(v)=1/.sqroot.2 for u,v=0, and PA1 c(u), c(v)=1 for u,v.noteq.0. PA1 x,y designate the coordinates of a datum in the data table, PA1 u,v designate the coordinates of a coefficient in the coefficient table, PA1 p(x,u)=c(u).multidot.cos[(2x+1)u.pi./2N] PA1 p(y,v)=c(v).multidot.cos[(2y+1)v.pi./2N] PA1 c(u), c(v)=1/.sqroot.2 for u,v=0, and c(u), c(v)=1 for u,v.noteq.0. PA1 for a first pair x,y, searching in a table for the absolute value and the sign of coefficient P=p(x,u).multidot.p(y,v); PA1 multiplying the absolute value of P by f(x,y); PA1 introducing the result of the multiplication by addition or subtraction (depending on the sign) in an accumulator; PA1 repeating the operation for all the values of the pair x,y; and PA1 extracting the result provided by the accumulator. PA1 searching in a first table, addressed by x and u, for the sign of p(x,u) and the value of an integer term n(x,u) (ranging from 1 to N-1), with: PA1 searching in a second table, addressed by y and v, for the sign of p(y,v) and the value of an integer term n(y,v) (ranging from 1 to n-1), with PA1 searching in a third table addressed by n(x,u) and n(y,v) for the absolute value of coefficient P. PA1 for four pairs x,y (corresponding to positions symmetrical by pairs with respect to central axes of the data table), searching in a table for the absolute value of coefficient P=p(x,u).multidot.p(y,v); PA1 combining by addition and/or subtraction, for these four pairs, the values of the corresponding data, the sign of each operation being determined as a function of the relative position of the four data; PA1 multiplying the combined value by the value of coefficient P; PA1 introducing the result of the multiplication into the accumulator; and PA1 repeating the operation for all pairs x,y with x and y ranging from 0 to (N/2)-1. PA1 addressing a location in the memory; PA1 providing the content of the location to a first input of a multiplier; PA1 storing in a first table, for all the values of the parameters n(x,u) and n(y,v) ranging from 1 to N-1, the values of ##EQU4## storing in second tables the values of the sign of the cosine functions as a function of the values of u and x, on the one hand and, v and y, on the other, as well as the values of n(x,u) and n(y,v) and using these values for addressing the first table; PA1 multiplying at each clock pulse a value of a location of the data block by a value of the first table; and PA1 cumulating the result of the multiplications by addition or subtraction as a function of the signs determined by the second tables for all the values of x and y. PA1 a data table memory; PA1 a memory of the products ##EQU5## where ##EQU6## and n(x,u) and n(y,v) are integers ranging from 1 to N-1; PA1 a table of the signs of p(x,u) and p(y,v) and values of n(x,u) and n(y,v) addressing the product memory; PA1 a coordinate generator sequentially providing value pair (u,v) and, for each pair (u,v), all the values of pair (x,y); PA1 a multiplier calculating the product of P by a data combination of the data memory; and a totalizer subtracting or adding the result of the multiplication with the previous results as a function of the sign provided by the sign table. PA1 x,y designate the coordinates of a datum in the data table, PA1 u,v designate the coordinates of a coefficient in the coefficient table, PA1 c(u), c(v)=1/.sqroot.2 for u,v=0 and PA1 c(u), c(v)=1 for u,v.noteq.0. PA1 a memory of the coefficient table; PA1 a memory of the products P=cos[n(x,u) .pi./2N].multidot.cos[n(y,v).pi./2N], where n(x,u) and n(y,v) are integers ranging from 1 to (N/2)-1; PA1 a table of the signs of cos[n(x,u).pi./2N] and cos[n(y,v).pi./2N] and of n(x,u) and n(y,v); PA1 a coordinate generator sequentially providing a pair of values (x,y) corresponding to the first quadrant of the data table as well as signals par(u) and par(v) equal to +1 or -1 depending on whether u and v are even or odd, and, for each pair (x,y), all the values of pair (u,v); PA1 a multiplier calculating the product of P by a coefficient combination of the coefficient memory; and PA1 four totalizers subtracting or adding the result of the multiplication from or to the previous results as a function of the sign provided by the sign table and the values of par(u) and par(v) for respectively providing f(x,y), f(x',y), f(x,y') and f(x',y') where x'=N-1-x and y'=N-1-y.
The calculation power required for DCT operation depends upon the number of blocks to be processed per second. For conventional or high definition TV images, several hundreds of kiloblocks must be processed per second; to achieve this purpose, one resorts to specialized integrated circuits implementing complex algorithm functions, such as the Byong Gi Lee algorithm. These circuits can achieve very fast processing operations, but unfortunately require numerous components to simultaneously achieve various operations. Such circuits therefore occupy a large surface on an integrated circuit, and are expensive.
Transform operations are also commonly needed at lower data rates, for example for processing images of the videophone type, for which processing of approximately 10 kiloblocks/second seems to be sufficient.
Thus, an object of the invention is to provide a method and a circuit for processing data through discrete cosine transform that can be achieved in the form of a small-size integrated circuit.
To achieve this object, the invention provides a DCT data processing method making the correspondence between an N.times.N table f(x,y) of data and an N.times.N table F(u,v) of coefficients according to the following relation: ##EQU3## where K is a constant power of 2,
This method is preferably, but not necessarily, implemented in a single integrated circuit.
The innovative method sequentially determines each coefficient F(u,v) for a coordinate pair (u,v) by performing the following steps:
According to an embodiment of the invention, the step of searching in a table is achieved as follows:
p(x,u)=Sgn[p(x,u)].multidot..vertline.cos[n(x,u).pi./2N].vertline.; PA2 p(y,v)=Sgn[p(y,v)].multidot..vertline.cos[n(y,v).pi./2N].vertline.; and
Another aspect of this method is to sequentially determine each coefficient F(u,v) by performing the following steps:
According to another approach, the invention provides a method for DCT processing of a block of N.times.N data points (f(x,y)) stored in a memory, where each location of the block corresponds to coordinates x,y, to provide a coefficient (F(u,v)) of a block of coefficients, the method comprising the following steps:
Another innovative teaching disclosed herein is a DCT data processing circuit, for making the correspondence between a table f(x,y) of N.times.N data and a table F(u,v) of N.times.N coefficients, which include:
Reciprocally, the disclosed innovations also provide a circuit for processing coefficients through reverse discrete cosine transform making the correspondence between a table of N.times.N coefficients (F(u,v)) and a table of N.times.N data (f(x,y)) according to the following relation: ##EQU7## where K is a constant power of 2,
This circuit comprises:
The disclosed innovations provide a particularly advantageous implementation of a videophone codec, wherein the Discrete DCT and the reverse DCT are performed on a single videocodec chip. The disclosed innovations help to provide a compact implementation of these functions at relatively low cost.